1. Field of the Invention
The present invention relates generally to combining switches used to support parallel processing. More particularly, the invention relates to a token ring switch wherein the processors within the ring combine operations (for example, Fetch-and-Add instructions), thereby reducing accesses to memory and allowing efficient implementation of processor synchronization.
2. Description of the Related Art
Gottlieb et al, in an article published in the February, 1983 IEEE Transactions On Computers (Vol. C-32, No. 2), entitled "The NYU Ultracomputer--Designing an MIMD Shared Memory Parallel Computer", describes the use of a multilevel switching network as a combining switch.
The machine described in the Gottlieb et al article implements a Fetch-and-Add instruction. The effect of this instruction when executed concurrently by N processors that attempt to update a single shared variable, is to combine the updating information in the switching network so that only a single access to physical memory is necessary to effect the N updates. A second effect of the instruction is that each of the N processors is returned a result that would have been observed for some serial ordering of the updates. Therefore the combining switch simulates the serial updating of the shared variable while actually performing the update in a parallel manner. The memory access rate is greatly reduced from the potential peak access rate and the processors can synchronize and serialize their actions where necessary, yet the time required for this to occur grows at most logarithmically in N.
The Gottlieb combining switch is inherently complex and costly, finding its principal application in supporting large numbers (hundreds or even thousands) of processing nodes. Many applications, such as local area networks, require the support of far fewer (e.g., usually less then fifty) processing nodes.
Well known ring networks, such as the token ring network described in the IEEE 802.5 standard, would be more suitable for such applications; however, the use of ring networks as both a combining switch and means for performing processor synchronization is heretofore unknown.
The concept of "modifying sums" as they pass around a token ring is described in an article by Livny et al, published by the IEEE in The Proceedings of the 1985 International Conference on Parallel Processing, in an article entitled "Shift Arithmetic On A Token Ring Network". Livny et al does not teach that a token ring can be used for synchronization nor does the prior art, in general, suggest implementing a Fetch-and-Add instruction in a ring context for the purpose of processor synchronization. Typically, synchronization in a ring is accomplished by other means, such as the passing of tokens.
Pfister et al, in an article published by the IEEE in The Proceedings of the 1985 International Conference on Parallel Processing, entitled "The IBM Research Parallel Processor Prototype (RP3); Introduction and Architecture", and U.S. Pat. No. 4,543,630, issued Sep. 24, 1985 to Neches, further exemplify the state of the art in switches that perform a combining function.
The combining switch taught by Pfister is an implementation of the Gottlieb et al machine. It too is complex and again directed toward handling a large number of processing nodes.
The Neches patent describes a tree network that may be used to synchronize multiple processors and can perform some data base operations, such as JOIN, in parallel across the network. However, when synchronization is performed in accordance with the Neches teachings, the synchronization operation forces serial operation of the processors, whereas when synchronization is done with Fetch-and-Add and a combining switch as taught by Gottlieb et al, the synchronization permits the processors to proceed immediately with parallel execution, unlike the teaching of Neches.
Accordingly, it would be desirable to be able to perform the synchronizing function using a combining switch that does not dictate serial processor operation, i.e., the switch should facilitate parallel processing while performing synchronization. Furthermore, it would be desirable if such switch were easier to implement than complex combining switches such as those described by Gottlieb et al and Pfister et al. Lower cost, increased reliability and minimizing required memory accesses would be further desirable features and by products of such a switch.
As used hereinafter, a "combining switch" shall be defined as a switch that receives requests to update a shared variable, and combines together update requests to the same shared variable so that the variable is updated only once.